package NC;

import java.util.ArrayList;
import java.util.Arrays;

// 回溯典型（选择，有重复）
public class NC46 {
    private ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
        Arrays.sort(num);
        backtrace(num,target,new ArrayList<>(),0,new boolean[num.length]);
        return ans;
    }
    public void backtrace(int[] num,int target,ArrayList<Integer> temp,int start,boolean[] flag){
        if(target<0) return;
        if(target ==0 ) {ans.add(new ArrayList<>(temp));return;}
        for (int i = start; i < num.length; i++) {
            if(i>start && num[i]==num[i-1]) continue; // 不让相同的值从同一层开始
            temp.add(num[i]);
            backtrace(num,target-num[i],temp,i+1,flag);
            temp.remove(temp.size()-1);
        }
    }
}

class Test6{
    public static void main(String[] args) {
        NC46 nc46 = new NC46();
        System.out.println(nc46.combinationSum2(new int[]{10, 1, 2, 7, 6, 1, 5}, 8));
    }

}